package com.banmoon.algorithm.leetcode;


public class Question29 {

    public static void main(String[] args) {
//        System.out.println(6 << 1);
//        System.out.println(other(0, 5, 2));
        System.out.println(divide(4, -3));
        System.out.println(divide(5, -8));
    }

    public static int divide(int dividend, int divisor) {
        long i = 0;
        boolean positive = dividend>=0 == divisor>=0;
        long lDividend = dividend;
        long lDivisor = divisor;
        lDividend = Math.abs(lDividend);
        lDivisor = Math.abs(lDivisor);

        if(positive==lDividend<lDivisor && lDividend<lDivisor)
            return 0;
        i = other(i, lDividend, lDivisor, lDivisor);
        long result = positive? i: 0-i;
        if(result>Integer.MAX_VALUE || result<Integer.MIN_VALUE)
            return Integer.MAX_VALUE;
        return (int) result;
    }

    private static long other(long i, long max, long min, long divisor){
        if(max < min)
            return 0;
        if(max-min<divisor)
            return 1;
        while (min<<1 <= max){
            i++;
            min = min<<1;
        }
        if(min!=max && min<<1 > max){
            return (long) Math.pow(2, i) + other(0, max - min, divisor, divisor);
        }
        return (long) Math.pow(2, i);
    }

}
